package proj2501.simple_module;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ComponentAdapter;
import java.awt.event.ComponentEvent;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;

import javax.imageio.ImageIO;
import javax.swing.AbstractAction;
import javax.swing.JFileChooser;
import javax.swing.JMenuItem;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JPopupMenu;
import javax.swing.SwingUtilities;

import proj2501.geo_util.Gr;
import proj2501.geo_util.LineSegmentD2;
import proj2501.geo_util.VectorD2;

class P008Puzzle15 extends JPanel {
	private static final int NUM_DEFAULT_SHUFFLE = 1000;
	private Random random = new Random();
	private boolean useGeneratedImage = true;
	private BufferedImage sourceImage;
	private BufferedImage zoomedImage;
	private int zoomedImageX;
	private int zoomedImageY;
	private int imageType = BufferedImage.TYPE_INT_ARGB;
	private int numTilesX = 4;
	private int numTilesY = 4;
	private double tileWidth;
	private double tileHeight;
	private boolean showDividers = false;
	private LinkedList<LineSegmentD2> dividersX = new LinkedList<LineSegmentD2>();
	private LinkedList<LineSegmentD2> dividersY = new LinkedList<LineSegmentD2>();
	private LinkedList<Tile> tiles = new LinkedList<Tile>();
	public P008Puzzle15() {
		addComponentListener(new ComponentAdapter() {
			@Override
			public void componentResized(ComponentEvent e) {
				super.componentResized(e);
				updateImages();
			}
		});
		addMouseListener(new MouseAdapter() {
			@Override
			public void mouseClicked(MouseEvent e) {
				super.mouseClicked(e);
				int clickedX = e.getX();
				int clickedY = e.getY();
				if (SwingUtilities.isLeftMouseButton(e)) {
					for (Tile tile: tiles) {
						Rectangle rect = tile.getScreenRect();
						if (rect.contains(clickedX, clickedY)) {
							System.out.println("Clicked Tile: " + tile.loc);
							tile.mouseClicked();
							break;
						}
					}
				} else if (SwingUtilities.isRightMouseButton(e)) {
					new PopupMenu().show(P008Puzzle15.this, clickedX, clickedY);
				}
			}
		});
		startGame();
	}
	private void updateImages() {
		initSourceImage();
		initZoomedImage();
		initDividers();
		updateTileImages();
		repaint();
	}
	private void initSourceImage() {
		if (useGeneratedImage) {
			int componentWidth = getWidth();
			int componentHeight = getHeight();
			double radius = Math.sqrt(Math.pow(componentWidth, 2) + Math.pow(componentHeight, 2));
			sourceImage = new BufferedImage(componentWidth, componentHeight, imageType);
			Graphics2D g = (Graphics2D) sourceImage.getGraphics();
			g.setColor(Color.LIGHT_GRAY);
			g.fillRect(0, 0, componentWidth, componentHeight);
			g.setColor(Color.BLACK);
			Gr gr = new Gr(g);
			VectorD2 center = new VectorD2(componentWidth / 2, componentHeight / 2);
			double step = 20;
			float penWidth = 5;
			g.setStroke(new BasicStroke(penWidth));
			for (double i = 0; i < radius; i += step) {
				gr.drawCircle(center, i);
			}
			g.dispose();
		}
	}
	private void initZoomedImage() {
		int componentWidth = getWidth();
		int componentHeight = getHeight();
		double componentRatio = (double) componentWidth / componentHeight;
		int sourceWidth = sourceImage.getWidth(null);
		int sourceHeight = sourceImage.getHeight(null);
		double sourceRatio = (double) sourceWidth / sourceHeight;
		int zoomedWidth;
		int zoomedHeight;
		if (useGeneratedImage) {
			zoomedWidth = componentWidth;
			zoomedHeight = componentHeight;
		} else {
			if (componentRatio >= sourceRatio) {
				zoomedHeight = componentHeight;
				zoomedWidth = (int) (zoomedHeight * sourceRatio);
				zoomedImageX = (int) ((double) componentWidth / 2 - zoomedWidth / 2);
				zoomedImageY = 0;
			} else {
				zoomedWidth = componentWidth;
				zoomedHeight = (int) (zoomedWidth / sourceRatio);
				zoomedImageX = 0;
				zoomedImageY = (int) ((double) componentHeight / 2 - zoomedHeight / 2);
			}
		}
		zoomedImage = new BufferedImage(zoomedWidth, zoomedHeight, imageType);
		Graphics2D g = (Graphics2D) zoomedImage.getGraphics();
		g.drawImage(sourceImage, 0, 0, zoomedWidth, zoomedHeight, null);
		g.dispose();
	}
	private void initDividers() {
		int zoomedWidth = zoomedImage.getWidth(null);
		int zoomedHeight = zoomedImage.getHeight(null);
		tileWidth = (double) zoomedWidth / numTilesX;
		tileHeight = (double) zoomedHeight / numTilesY;
		dividersX.clear();
		for (int i = 0; i <= numTilesX; i++) {
			double x = zoomedImageX + tileWidth * i;
			double y2 = zoomedImageY + zoomedHeight;
			LineSegmentD2 line = new LineSegmentD2(x, zoomedImageY, x, y2);
			dividersX.add(line);
		}
		dividersY.clear();
		for (int i = 0; i <= numTilesY; i++) {
			double y = zoomedImageY + tileHeight * i;
			double x2 = zoomedImageX + zoomedWidth;
			LineSegmentD2 line = new LineSegmentD2(zoomedImageX, y, x2, y);
			dividersX.add(line);
		}
	}
	private void updateTileImages() {
		for (Tile tile: tiles) {
			int cornerX = (int) (tile.defaultLoc.getX() * tileWidth);
			int cornerY = (int) (tile.defaultLoc.getY() * tileHeight);
			int nextX = (int) ((tile.defaultLoc.getX() + 1) * tileWidth);
			int nextY = (int) ((tile.defaultLoc.getY() + 1) * tileHeight);
			Rectangle rect = new Rectangle(cornerX, cornerY, nextX - cornerX, nextY - cornerY);
			tile.imageRect = rect;
		}
	}
	private void startGame() {
		System.out.println("Starting a game.");
		initTiles();
		shuffle();
	}
	private void shuffle(int numMove) {
		int numMoved = 0;
		System.out.println("Executing shuffle method.");
		while (true) {
			if (numMove <= numMoved) {
				break;
			}
			List<VectorD2> movableLocs = getMovableLocs();
			int randomIndex = random.nextInt(movableLocs.size());
			VectorD2 loc = movableLocs.get(randomIndex);
			Tile tile = getTile(loc.getX(), loc.getY());
			tile.move();
			numMoved++;
		}
		System.out.println("  " + numMoved + " moves done. Shuffling finished.");
	}
	private void shuffle() { shuffle(NUM_DEFAULT_SHUFFLE); }
	private void initTiles() {
		tiles.clear();
		for (int y = 0; y < numTilesY; y++) {
			for (int x = 0; x < numTilesX; x++) {
				Tile tile = new Tile();
				tile.loc = tile.defaultLoc = new VectorD2(x, y);
				if (x == numTilesX - 1 && y == numTilesY - 1) {
					tile.isBlank = true;
				}
				tiles.add(tile);
			}
		}
	}
	@Override
	protected void paintComponent(Graphics g) {
		super.paintComponent(g);
		if (sourceImage == null) {
			System.out.println("imageBuffer is null.");
			return;
		}
		Graphics2D g2 = (Graphics2D) g;
		int w = getWidth();
		int h = getHeight();
		Gr gr = new Gr(g2);
		g2.setColor(Color.GRAY);
		g2.fillRect(0, 0, w, h);
		for (Tile tile: tiles) {
			int cornerX = zoomedImageX + (int) (tile.loc.getX() * tileWidth);
			int cornerY = zoomedImageY + (int) (tile.loc.getY() * tileHeight);
			int nextX = zoomedImageX + (int) ((tile.loc.getX() + 1) * tileWidth);
			int nextY = zoomedImageY + (int) ((tile.loc.getY() + 1) * tileHeight);
			if (tile.isBlank && ! isCleared()) {
				g2.setColor(Color.DARK_GRAY);
				g2.fillRect(cornerX, cornerY, nextX - cornerX, nextY - cornerY);
			} else {
				Rectangle rect = tile.imageRect;
				g2.drawImage(zoomedImage, cornerX, cornerY, nextX, nextY,
						rect.x, rect.y, rect.x + rect.width, rect.y + rect.height, null);
			}
		}
		
		if (showDividers) {
			float penWidth = 4;
			g2.setStroke(new BasicStroke(penWidth));
			g2.setColor(Color.BLACK);
			for (LineSegmentD2 line : dividersX) {
				gr.drawLine(line);
			}
			for (LineSegmentD2 line : dividersY) {
				gr.drawLine(line);
			}
		}
	}
	private class Tile {
		VectorD2 defaultLoc;
		VectorD2 loc;
		boolean isBlank;
		Rectangle imageRect;
		private boolean canMove() {
			if (isBlank) {
				return false;
			}
			VectorD2 blank = getBlankLoc();
			if (blank.getX() == loc.getX() || blank.getY() == loc.getY()) {
				return true;
			}
			return false;
		}
		public Rectangle getScreenRect() {
			int x = zoomedImageX + (int) (loc.getX() * tileWidth);
			int y = zoomedImageY + (int) (loc.getY() * tileHeight);
			Rectangle rect = new Rectangle(x, y, (int) tileWidth, (int) tileHeight);
			return rect;
		}
		public void mouseClicked() {
			if (canMove()) {
				move();
			}
		}
		private void move() {
			Tile blankTile = getBlankTile();
			VectorD2 blankLoc = blankTile.loc;
			double blankX = blankLoc.getX();
			double blankY = blankLoc.getY();
			double nearX = loc.getX();
			double nearY = loc.getY();
			if (blankX < nearX) {
				nearX--;
			} else if (nearX < blankX) {
				nearX++;
			}
			if (blankY < nearY) {
				nearY--;
			} else if (nearY < blankY) {
				nearY++;
			}
			if (nearX == blankX && nearY == blankY) {
				swapLoc(blankTile);
			} else {
				Tile nearTile = getTile(nearX, nearY);
				nearTile.move();
				swapLoc(blankTile);
			}
			repaint();
			if (isCleared()) {
				System.out.println("Congratulations.");
			}
		}
		private void swapLoc(Tile tile) {
			VectorD2 temp = loc;
			this.loc = tile.loc;
			tile.loc = temp;
		}
	}
	private Tile getBlankTile() {
		for (Tile tile: tiles) {
			if (tile.isBlank) {
				return tile;
			}
		}
		return null;
	}
	private VectorD2 getBlankLoc() { return getBlankTile().loc; }
	private Tile getTile(double x, double y) {
		for (Tile tile: tiles) {
			if (tile.loc.getX() == x && tile.loc.getY() == y) {
				return tile;
			}
		}
		return null;
	}
	private boolean isCleared() {
		for (Tile tile: tiles) {
			if (tile.loc.equals(tile.defaultLoc)) {
				
			} else {
				return false;
			}
		}
		return true;
	}
	private List<VectorD2> getMovableLocs() {
		List<VectorD2> list = new LinkedList<VectorD2>();
		int blankX = (int) getBlankLoc().getX();
		int blankY = (int) getBlankLoc().getY();
		for (int x = 0; x < numTilesX; x++) {
			if (x != blankX) {
				list.add(new VectorD2(x, blankY));
			}
		}
		for (int y = 0; y < numTilesY; y++) {
			if (y != blankY) {
				list.add(new VectorD2(blankX, y));
			}
		}
		return list;
	}
	private class PopupMenu extends JPopupMenu {
		public PopupMenu() {
			JMenuItem item;
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Shuffle") {
				@Override
				public void actionPerformed(ActionEvent e) {
					int result = JOptionPane.showConfirmDialog(P008Puzzle15.this, "Really?");
					if (result == JOptionPane.OK_OPTION) {
						shuffle();
					}
				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Shuffle (N times)...") {
				@Override
				public void actionPerformed(ActionEvent e) {
					String input = JOptionPane.showInputDialog(P008Puzzle15.this, "Number of random movements:", "" + NUM_DEFAULT_SHUFFLE);
					if (input != null) {
						int num = 0;
						boolean failed = false;
						try {
							num = Integer.parseInt(input);
						} catch (NumberFormatException ex) {
							failed = true;
						}
						if (! failed) {
							if (1 <= num) {
								shuffle(num);
							} else {
								failed = true;
							}
						}
						if (failed) {
							JOptionPane.showMessageDialog(P008Puzzle15.this, "Failed.");
						}
					}

				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Show/Hide Grid") {
				@Override
				public void actionPerformed(ActionEvent e) {
					showDividers = ! showDividers;
					P008Puzzle15.this.repaint();
				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Load Image") {
				@Override
				public void actionPerformed(ActionEvent e) {
					JFileChooser chooser = new JFileChooser();
					int result = chooser.showOpenDialog(P008Puzzle15.this);
					if (result == JFileChooser.APPROVE_OPTION) {
						File file = chooser.getSelectedFile();
						System.out.println("Loading file: " + file);
						boolean failedToRead = false;
						BufferedImage image = null;
						try {
							image = ImageIO.read(file);
						} catch (IOException e1) {
							failedToRead = true;
						}
						if (image == null) {
							failedToRead = true;
						}
						if (failedToRead) {
							JOptionPane.showMessageDialog(P008Puzzle15.this, "Failed to load image from the file.");
						} else {
							useGeneratedImage = false;
							sourceImage = image;
							startGame();
							updateImages();
						}
					}
				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Change Number of Horizontal Tiles") {
				@Override
				public void actionPerformed(ActionEvent e) {
					String input = JOptionPane.showInputDialog(P008Puzzle15.this, "Number of horizontal tiles:", "" + numTilesX);
					if (input != null) {
						int num = 0;
						boolean failed = false;
						try {
							num = Integer.parseInt(input);
						} catch (NumberFormatException ex) {
							failed = true;
						}
						if (! failed) {
							if (2 <= num) {
								numTilesX = num;
								startGame();
								updateImages();
							} else {
								failed = true;
							}
						}
						if (failed) {
							JOptionPane.showMessageDialog(P008Puzzle15.this, "Failed.");
						}
					}
				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Change Number of Vertical Tiles") {
				@Override
				public void actionPerformed(ActionEvent e) {
					String input = JOptionPane.showInputDialog(P008Puzzle15.this, "Number of vertical tiles:", "" + numTilesY);
					if (input != null) {
						int num = 0;
						boolean failed = false;
						try {
							num = Integer.parseInt(input);
						} catch (NumberFormatException ex) {
							failed = true;
						}
						if (! failed) {
							if (2 <= num) {
								numTilesY = num;
								startGame();
								updateImages();
							} else {
								failed = true;
							}
						}
						if (failed) {
							JOptionPane.showMessageDialog(P008Puzzle15.this, "Failed.");
						}
					}
				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Breadth First Search (This will freeze computer.)") {
				@Override
				public void actionPerformed(ActionEvent e) {
					Queue<Snap> queue = new LinkedList<Snap>();
					queue.add(createSnapFromCurrentGame());
					Snap answer = null;
					int numCheck = 0;
					int numCheckPrev = 0;
					int advance = 0;
					long before = System.currentTimeMillis();
					long lastOutput = before;
					System.out.println(new Date(before));
					Snap snap;
					while (true) {
						snap = queue.poll();
						if (snap == null) {
							System.out.println("empty.");
							break;
						}
						if (snap.isVisited()) {
							continue;
						}
						numCheck++;
						long current = System.currentTimeMillis();
						if (current - lastOutput >= 1000) {
							advance = numCheck - numCheckPrev;
							System.out.println("Trying: " + numCheck + " (Generation: " + snap.generation + ", Queue Size:" + queue.size() + ", Advance: " + advance + ")");
							if (advance < 10000) {
								System.out.println("Low performance.");
								System.out.println("Aborting.");
								break;
							}
							lastOutput = current;
							numCheckPrev = numCheck;
						}
						if (snap.isSolved()) {
							System.out.println("Solved.");
							answer = snap;
							break;
						}
						for (Snap child: snap.getChildren()) {
							queue.add(child);
						}
					}
					System.out.println("Search finished: " + numCheck);
					System.out.println("ans: " + answer);
				}
			});
			add(item);
			
			item= new JMenuItem();
			item.setAction(new AbstractAction("Depth First Search? (This will freeze computer.)") {
				@Override
				public void actionPerformed(ActionEvent e) {
					Deque<Snap> stack = new ArrayDeque<Snap>();
					HashSet<Snap> visited = new HashSet<Snap>();
					Snap currentSnap = createSnapFromCurrentGame();
					visited.add(currentSnap);
					stack.push(currentSnap);
					Snap answer = null;
					int numCheck = 0;
					int numCheckPrev = 0;
					int advance = 0;
					long before = System.currentTimeMillis();
					long lastOutput = before;
					System.out.println(new Date(before));
					Snap snap;
					while (true) {
						if (stack.isEmpty()) {
							System.out.println("empty.");
							break;
						}
						snap = stack.pop();
//						if (snap.isVisited()) {
//							continue;
//						}
						numCheck++;
						long current = System.currentTimeMillis();
						if (current - lastOutput >= 1000) {
							advance = numCheck - numCheckPrev;
							System.out.println("Trying: " + numCheck + " (Generation: " + snap.generation + ", Stack Size:" + stack.size() + ", Advance: " + advance + ")");
//							if (advance < 10000) {
//								System.out.println("Low performance.");
//								System.out.println("Aborting.");
//								break;
//							}
							lastOutput = current;
							numCheckPrev = numCheck;
						}
						if (snap.isSolved()) {
							System.out.println("Solved.");
							System.out.println("Generation: " + snap.generation);
							answer = snap;
							break;
						}
						for (Snap child: snap.getSortedChildren()) {
							if (! visited.contains(child)) {
								visited.add(child);
								stack.push(child);
							}
						}
					}
					System.out.println("Search finished: " + numCheck);
					System.out.println("ans: " + answer);
				}
			});
			add(item);
		}
	}
	
	private class Snap {
		Snap parent;
		/* If there are 4x4 tiles, (x=0, y=0) represents the top left cell, and (x=3, y=3) represents the bottom right cell.
		 * And with this variable "cells", cells[0] represents (x=0, y=0), cells[1] represents (x=1, y=0),
		 * cells[4] represents (x=0, y=1), cells[15] represents (x=3, y=3).
		 * When the puzzle solved, cells[0] has value 0, cells[1] has value 1 ..., cells[15] has value 15. */
		int[] cells;
		int blankCurrentLoc;
		int generation;
		public Snap() {
			int numTiles = numTilesX * numTilesY;
			cells = new int[numTiles];
		}
		@Override
		public String toString() {
			String s = "";
			for (int i = 0; i < cells.length; i++) {
				s += cells[i];
				if (i % numTilesX == numTilesX - 1) {
					s += ",";
					if (i != numTilesX * numTilesY - 1) {
						s += "\n";
					}
				} else {
					s += ", ";
				}
			}
			return s;
		}
		public boolean equals(Snap snap) {
			for (int i = 0; i < cells.length; i++) {
				if (cells[i] != snap.cells[i]) {
					return false;
				}
			}
			return true;
		}
		private Snap swap(int notBlankCellLoc) {
			Snap snap = new Snap();
			snap.parent = this;
			System.arraycopy(cells, 0, snap.cells, 0, cells.length);
			snap.cells[blankCurrentLoc] = snap.cells[notBlankCellLoc];
			snap.cells[notBlankCellLoc] = blankDefaultLoc;
			snap.blankCurrentLoc = notBlankCellLoc;
			snap.generation = this.generation + 1;
			return snap;
		}
		public List<Snap> getChildren() {
			List<Snap> list = new LinkedList<Snap>();
			if (blankCurrentLoc % numTilesX != 0) {
				list.add(swap(blankCurrentLoc - 1));
			}
			if (blankCurrentLoc % numTilesX != numTilesX - 1) {
				list.add(swap(blankCurrentLoc + 1));
			}
			if (blankCurrentLoc / numTilesX != 0) {
				list.add(swap(blankCurrentLoc - numTilesX));
			}
			if (blankCurrentLoc / numTilesX != numTilesY - 1) {
				list.add(swap(blankCurrentLoc + numTilesX));
			}
			return list;
		}
		public boolean isVisited() {
			Snap ancestor = parent;
			while (ancestor != null) {
				if (ancestor.equals(this)) {
					return true;
				}
				ancestor = ancestor.parent;
			}
			return false;
		}
		public boolean isSolved() {
			for (int i = 0; i < cells.length; i++) {
				if (cells[i] != i) {
					return false;
				}
			}
			return true;
		}
		public int getScore() {
			int score = 0;
			for (int i = 0; i < cells.length; i++) {
				int cellX = i % numTilesX;
				int tileX = cells[i] % numTilesX;
				int distanceX = Math.abs(tileX - cellX);
				score -= distanceX;
				int cellY = i / numTilesY;
				int tileY = cells[i] / numTilesY;
				int distanceY = Math.abs(tileY - cellY);
				score -= distanceY;
			}
			return score;
		}
		public List<Snap> getSortedChildren() {
			List<Snap> list = getChildren();
			Collections.sort(list, new Comparator<Snap>() {
				@Override
				public int compare(Snap snap1, Snap snap2) {
					return snap1.getScore() - snap2.getScore();
				}
			});
			return list;
		}
		@Override
		public int hashCode() {
			int hashCode = 0;
			for (int i = 0; i < cells.length; i++) {
				hashCode += cells[i] + cells[i] * i;
				hashCode <<= 1;
			}
			return hashCode;
		}
		@Override
		public boolean equals(Object obj) {
			if (! (obj instanceof Snap)) {
				return false;
			}
			Snap snap = (Snap) obj;
			for (int i = 0; i < cells.length; i++) {
				if (cells[i] != snap.cells[i]) {
					return false;
				}
			}
			return true;
		}
	}
	int blankDefaultLoc;
	public Snap createSnapFromCurrentGame() {
		Snap snap = new Snap();
		for (Tile tile: tiles) {
			int dx = (int) tile.defaultLoc.getX();
			int dy = (int) tile.defaultLoc.getY();
			int dIndex = numTilesX * dy + dx;
			int cx = (int) tile.loc.getX();
			int cy = (int) tile.loc.getY();
			int cIndex = numTilesX * cy + cx;
			snap.cells[cIndex] = dIndex;
			if (tile.isBlank) {
				blankDefaultLoc = dIndex;
				snap.blankCurrentLoc = cIndex;
			}
		}
		return snap;
	}
}
